package com.mlh.greed;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author 缪林辉
 * @date 2024/4/15 10:40
 * @DESCRIPTION
 */
// 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。
// 返回 需要移除区间的最小数量，使剩余区间互不重叠 。
// 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
// 输出: 1
// 解释: 移除 [1,3] 后，剩下的区间没有重叠。
public class 无重叠区间 {
    public static int method1(int[][] intervals) {
        //排序
        Arrays.sort(intervals, (o1, o2) -> {
            // 写出这样很耗时，在知道没有重复值的情况下，直接用Integer.compare(o1[0],o2[0]);
            // if(o1[0]>o2[0]){
            //     return 1;
            // }else if(o1[0]==o2[0]&&o1[1]<o2[1]){
            //     return 1;
            // }else{
            //     return -1;
            // }
            return Integer.compare(o1[0],o2[0]);
        });
        // 贪心策略：这题和射气球的思路非常的接近
        //先排序，然后我这里使用右边界来排除重叠空间
        //看edge是否小于区间的左边界，小于的话，说明无重叠，去更新edge
        //大于的话，说明发生了重叠需要删除一个区间，删除谁呢？
        //需要去判断edge是否大于该区间的右边界，删除右边界大的，这样更能够降低重叠的可能性
        int delNum=0;//记录要删除的区间数
        int edge=intervals[0][1];//记录某区间的右边界
        for (int i = 1; i < intervals.length; i++) {
            if(edge>intervals[i][0]){
                if(edge>intervals[i][1]){
                    edge=intervals[i][1];
                }
                delNum++;
            }else{
                edge=intervals[i][1];
            }
        }
        return delNum;
    }

    // public static void main(String[] args) {
    //     int[][] intervals={{-52, 31}, {-73, -26}, {82, 97}, {-65, -11}, {-62, -49}, {95, 99}, {58, 95}, {-31, 49}, {66, 98}, {-63, 2}, {30, 47}, {-40, -26}};
    //     method1(intervals);
    // }
}
